package com.ztom.v2;

import java.util.HashSet;
import java.util.Set;

/**
 * @author ZhangTao
 */
public class Code03LongestConsecutiveSequence {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 1) {
            return 1;
        }

        // 找子序列, 直接先去重
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int max = 0;
        for (int num : set) {
            // 剪枝: 前面计算过的一定比以当前为序列头得到结果的长
            if (set.contains(num - 1)) {
                continue;
            }
            // 计算当前值为序列头
            int count = 1;
            int tmp = num;
            while (set.contains(++tmp)) {
                count++;
            }
            max = Math.max(max, count);
        }

        return max;
    }
}
